// 可以删除某项
// 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。


// 输入：s = "bbbab"
// 输出：4
// 解释：一个可能的最长回文子序列为 "bbbb" 。


// https://leetcode.cn/problems/longest-palindromic-subsequence/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-dpzi-dv83q/
// 动态规划
// 1. 确定dp数组（dp table）以及下标的含义
// dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

// 2. 确定递推公式（见解析图理解）
// 如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;

// 如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
// 加入s[j]的回文子序列长度为dp[i + 1][j]。
// 加入s[i]的回文子序列长度为dp[i][j - 1]。
// 那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

// 3. dp数组如何初始化
// i和j 保证不会相等，倒叙循环，以及循环开始j= n+1 开始，递推公式保证


// 4. 确定遍历顺序
// 从递推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 可以看出，dp[i][j]是依赖于dp[i + 1][j - 1] 和 dp[i + 1][j]，
// 也就是从矩阵的角度来说，dp[i][j] 下一行的数据。 所以遍历i的时候一定要从下到上遍历，这样才能保证，下一行的数据是经过计算的。

// 5. 举例推导dp数组（见链接图）


const longestPalindromeSubseq = (s) => {
    const strLen = s.length;
    let dp = Array.from(Array(strLen), () => Array(strLen).fill(0));
    
    for(let i = 0; i < strLen; i++) {
        dp[i][i] = 1;
    }

    for(let i = strLen - 1; i >= 0; i--) {
        for(let j = i + 1; j < strLen; j++) {
            if(s[i] === s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }

    return dp[0][strLen - 1];
};